package algorithms.question.class14;

import common.util.MyUtil;

import java.util.TreeSet;

/**
 * 请返回arr中，求子数组的累加和<=K的并且是最大的
 * 返回这个最大的累加和
 *
 * @author guichang
 * @date 2021/8/11
 */

@SuppressWarnings("all")
public class Code2_小于等于K的最大的累加和 {

    public static void main(String[] args) {
        int[] arr = MyUtil.createRandomArray(10, -5, 10);
        MyUtil.print(latestK(arr, 8));
    }

    public static int latestK(int[] arr, int K) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        // 以i结尾的子数组累加和<=K求解可转换为(0~i的前缀和)>=(i的前缀和-K)
        TreeSet<Integer> set = new TreeSet<>();
        // 一个数也没有的情况下的前缀和
        set.add(0);
        int ans = Integer.MIN_VALUE;
        int sumi = 0;
        for (int i = 0; i < arr.length; i++) {
            sumi += arr[i];
            Integer ceiling = set.ceiling(sumi - K);
            if(ceiling != null) {
                ans = Math.max(ans, sumi - ceiling);
            }
            set.add(sumi);
        }
        return ans;
    }

}